This invention relates to search engines for searching large tables of data, and particularly to an improved protocol for insertion and deletion of items to the search table.
Lookup procedures are a major source of bottlenecks in high-performance compilers and routers, such as compilers used to search databases of cell designs for designing integrated circuits, and compilers used to lookup internet addresses (URLs) in network applications. Recently, there has been renewed interest in binary search trees, largely because the worst-case time required for basic dynamic set operations is O(log n), where n is the number of nodes or vertices in the tree. In application Ser. No. 09/679,313, we describe a sorted binary search tree that inherits the favorable attributes of prior binary search trees, but provides simpler solutions for insertion and deletion functions. However, that search tree requires considerable memory allocation, particularly for performing insertion and deletion functions. The insertion and deletion functions are important to the search tree because they maintain equal length to all search paths through the tree.
The present invention is directed to an improvement of the search tree described in our aforementioned applications, and particularly to an improved insertion and deletion technique that reduces memory requirements for the tree.
One aspect of the present invention is a process for changing the number of entries in a search tree by inserting or deleting entries into or from a vertex of a bottom level. The search tress has a top level, a bottom level and at least one hierarchy level between the top level and the bottom level. The bottom level has a plurality of vertices each containing at least one entry, with each bottom level vertex being a child vertex to a vertex of a hierarchy level and each vertex in the top and hierarchy levels being a parent to at least one vertex in a lower level. A vertex is selected and its level in the tree identified. If the level of the selected vertex is not the bottom level, the entries in the child vertices of the selected vertex are redistributed so that the child vertex having a maximal index contains a predetermined number of entries. In the case of a deletion, the predetermined number equals the maximum number H that a vertex may contain. In the case of an insertion, the predetermined number is less than the maximum number and is preferably Hxe2x88x921. If the level of the child vertex is the bottom level the entry is inserted or deleted on the child vertex having the maximal index. If the level of the selected vertex is the bottom level the entry is inserted or deleted on the selected vertex.
In preferred forms of the invention, the process of deleting an entry from the search tree is performed by repeating the steps of the process using the child vertex having the maximal index found during one iteration for the selected vertex during the next iteration, until a child vertex is found in the bottom level.
In preferred forms of the invention, if the level of the child vertex is not the bottom level, the process of inserting an entry to the search tree is includes redistributing entries between grandchild vertices of the selected vertex that are children of the child vertex having the maximal index so that the grandchild vertex having a maximal index contains the predetermined number of entries. If the level of the grandchild vertex is the bottom level the entry is inserted on the grandchild vertex having the maximal index. If the level of the grandchild vertex is not the bottom vertex, the process is repeated using the child or grandchild vertex having the maximal index found during one iteration for the selected vertex during the next iteration, until a child or grandchild vertex is found in the bottom level.
The selection of the child or grandchild vertex as the selected vertex depends on whether the child vertex contains the maximum number (H) of entries. If the child vertex contains less than the maximum number of entries (Hxe2x88x921), the process is repeated using the child vertex during the next iteration. If the child vertex contains the maximum number of entries (H), the process is repeated using the grandchild vertex during the next iteration.
Another aspect of the present invention resides in a search tree that includes instrumentalities to carry out the process of the invention.
Another aspect of the present invention resides in the provision of computer readable program code that is embedded in a computer usable medium. The computer readable program code includes computer code that causes a computer to define the search tree and computer code that causes the computer to insert and delete entries to and from bottom vertices of the tree.